#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

#include "securec.h"
#include "treeUtils.h"
typedef struct queNode {
    int val;
    struct TreeNode *node;
    struct queNode *next;
} queNode;

void init(struct queNode **p, int val, struct TreeNode *node) {
    (*p) = (struct queNode *)malloc(sizeof(struct queNode));
    (*p)->val = val;
    (*p)->node = node;
    (*p)->next = NULL;
}

bool hasPathSum(struct TreeNode *root, int sum) {
    if (root == NULL) {
        return false;
    }
    struct queNode *queLeft, *queRight;
    init(&queLeft, root->val, root);
    queRight = queLeft;
    while (queLeft != NULL) {
        struct TreeNode *now = queLeft->node;
        int temp = queLeft->val;
        if (now->left == NULL && now->right == NULL) {
            if (temp == sum) return true;
        }
        if (now->left != NULL) {
            init(&queRight->next, now->left->val + temp, now->left);
            queRight = queRight->next;
        }
        if (now->right != NULL) {
            init(&queRight->next, now->right->val + temp, now->right);
            queRight = queRight->next;
        }
        queLeft = queLeft->next;
    }
    return false;
}

int main()
{
    setbuf(stdout, 0);
    char str[] = "[5,4,8,11,null,13,4,7,2,null,null,null,1]";
    printf("%s\n", "start strtok string.");
    int count = 0;
    char retStrArr[100][10] = {0};
    getNum(str, retStrArr, &count);
    int numArr[9] = {0};
    for (int i = 0; i < count; ++i) {
        printf("%s\n", retStrArr[i]);
        numArr[i] = atoi(retStrArr[i]);
    }
    printf("%s\n", "end strtok string.");

    struct TreeNode *root = malloc(sizeof(struct TreeNode));
    root->val = numArr[0];
    root->left = NULL;
    root->right = NULL;
    bfsBuildTree(root, numArr, count);
    numArr[4] = 0;
    struct TreeNode *root1 = malloc(sizeof(struct TreeNode));
    root1->val = numArr[0];
    root1->left = NULL;
    root1->right = NULL;
    bfsBuildTree(root1, numArr, count);
    int ret = hasPathSum(root, 21);
    printf("%s", ret ? "true" : "false");
}